home *** CD-ROM | disk | FTP | other *** search
/ Aminet 34 / Aminet 34 (2000)(Schatztruhe)[!][Dec 1999].iso / Aminet / util / gnu / unixcmds.lha / unixcmds / src / expr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-06  |  17.6 KB  |  660 lines
  1. /*
  2. FUNCTIONS
  3. This source file includes following functions.
  4. numresult
  5. main
  6. expr1
  7. expr2
  8. RELOP
  9. expr3
  10. BINOP
  11. expr4
  12. expr5
  13. expr6
  14. expr7
  15. nullz
  16. numvalue
  17. strvalue
  18. strsave
  19. invalid
  20. docolon
  21. rcomp
  22. rmatch
  23. rtry
  24. tryone
  25. */
  26.  
  27. /* expr  - expression evaluator for shell       Author: Peter S. Housel */
  28.  
  29. #include <string.h>
  30. #include <ctype.h>
  31. #include <stdlib.h>
  32. #include <stdio.h>
  33.  
  34. struct value {
  35.   long numval;                  /* numeric value */
  36.   int nf_valid;                 /* "numeric value field valid" flag */
  37.   char *strval;                 /* string value */
  38. };
  39.  
  40. #define numresult(valp,number)    (((valp)->nf_valid = 1),((valp)->strval = NULL),((valp)->numval = (number)))
  41.  
  42. int main  (int argc, char **argv);
  43. void expr1  (struct value *valp);
  44. void expr2  (struct value *valp);
  45. void expr3  (struct value *valp);
  46. void expr4  (struct value *valp);
  47. void expr5  (struct value *valp);
  48. void expr6  (struct value *valp);
  49. void expr7  (struct value *valp);
  50. int nullz  (struct value *valp);
  51. int numvalue  (struct value *valp);
  52. char *strvalue  (struct value *valp);
  53. char *strsave  (char *string);
  54. void invalid  (char *err);
  55. void docolon  (struct value *match, struct value *pattern);
  56. void rcomp  (char *regexp);
  57. void rmatch  (char *str);
  58. char *rtry  (char *str, unsigned char **pcp);
  59. char *tryone  (char *str, unsigned char **pcp);
  60.  
  61. char *progname;
  62. char **argp;
  63. char NUMARG[] = "numeric argument required";
  64.  
  65. int main(argc, argv)
  66. /* [<][>][^][v][top][bottom][index][help] */
  67. int argc;
  68. char *argv[];
  69. {
  70.   struct value val0;
  71.  
  72.   progname = argv[0];
  73.   argp = &argv[1];
  74.   expr1(&val0);
  75.   if (*argp != NULL) invalid("syntax error");
  76.   (void) puts(strvalue(&val0));
  77.   return(nullz(&val0));
  78. }
  79.  
  80. /* Yet Another recursive descent parser. */
  81. void expr1(valp)
  82. /* [<][>][^][v][top][bottom][index][help] */
  83. struct value *valp;
  84. {
  85.   struct value val1;
  86.  
  87.   expr2(valp);
  88.  
  89.   while (*argp != NULL) {
  90.         if (strcmp(*argp, "|") == 0) {
  91.                 ++argp;
  92.                 expr2(&val1);
  93.                 if (nullz(valp))
  94.                         *valp = val1;
  95.                 else;           /* return the first arg (already in *valp) */
  96.         } else
  97.                 break;
  98.   }
  99. }
  100.  
  101. void expr2(valp)
  102. /* [<][>][^][v][top][bottom][index][help] */
  103. struct value *valp;
  104. {
  105.   struct value val1;
  106.  
  107.   expr3(valp);
  108.  
  109.   while (*argp != NULL) {
  110.         if (strcmp(*argp, "&") == 0) {
  111.                 ++argp;
  112.                 expr3(&val1);
  113.                 if (nullz(valp) && nullz(&val1))
  114.                         numresult(valp, 0);
  115.                 else;           /* return the first arg (already in *valp) */
  116.         } else
  117.                 break;
  118.   }
  119. }
  120.  
  121. /* Save source code lines but not object code, unfortunately. */
  122.  
  123. #define RELOP(OP) ++argp;expr4(&val1);if(numvalue(valp) && numvalue(&val1)) numresult(valp, valp->numval OP val1.numval); else numresult(valp, strcmp(strvalue(valp), strvalue(&val1)) OP 0);
  124.  
  125. void expr3(valp)
  126.  
  127. struct value *valp;
  128. {
  129.   struct value val1;
  130.  
  131.   expr4(valp);
  132.  
  133.   while (*argp != NULL) {
  134.         if (strcmp(*argp, "<") == 0) {
  135.                 RELOP(<)
  136.         } else if (strcmp(*argp, "<=") == 0) {
  137.                 RELOP(<=)
  138.         } else if (strcmp(*argp, "=") == 0) {
  139.                 RELOP(==)
  140.         } else if (strcmp(*argp, "!=") == 0) {
  141.                 RELOP(!=)
  142.         } else if (strcmp(*argp, ">=") == 0) {
  143.                 RELOP(>=)
  144.         } else if (strcmp(*argp, ">") == 0) {
  145.                 RELOP(>)
  146.         } else
  147.                 break;
  148.   }
  149. }
  150.  
  151. #define BINOP(NEXT,OP) ++argp;NEXT(&val1);if(!numvalue(valp) || !numvalue(&val1)) invalid(NUMARG); else numresult(valp, valp->numval OP val1.numval);
  152.  
  153.  
  154. void expr4(valp)
  155. struct value *valp;
  156. {
  157.   struct value val1;
  158.  
  159.   expr5(valp);
  160.  
  161.   while (*argp != NULL) {
  162.         if (strcmp(*argp, "+") == 0) {
  163.                 BINOP(expr5, +)
  164.         } else if (strcmp(*argp, "-") == 0) {
  165.                 BINOP(expr5, -)
  166.         } else
  167.                 break;
  168.   }
  169. }
  170.  
  171. void expr5(valp)
  172. /* [<][>][^][v][top][bottom][index][help] */
  173. struct value *valp;
  174. {
  175.   struct value val1;
  176.  
  177.   expr6(valp);
  178.  
  179.   while (*argp != NULL) {
  180.         if (strcmp(*argp, "*") == 0) {
  181.                 BINOP(expr6, *)
  182.         } else if (strcmp(*argp, "/") == 0) {
  183.                 ++argp;
  184.                 expr6(&val1);
  185.                 if (!numvalue(valp) || !numvalue(&val1))
  186.                         invalid(NUMARG);
  187.                 else {
  188.                         if (val1.numval == 0) invalid("division by zero");
  189.                         numresult(valp, valp->numval / val1.numval);
  190.                 }
  191.         } else if (strcmp(*argp, "%") == 0) {
  192.                 ++argp;
  193.                 expr6(&val1);
  194.                 if (!numvalue(valp) || !numvalue(&val1))
  195.                         invalid(NUMARG);
  196.                 else {
  197.                         if (val1.numval == 0) invalid("division by zero");
  198.                         numresult(valp, valp->numval % val1.numval);
  199.                 }
  200.         } else
  201.                 break;
  202.   }
  203. }
  204.  
  205. void expr6(valp)
  206. /* [<][>][^][v][top][bottom][index][help] */
  207. struct value *valp;
  208. {
  209.   struct value val1;
  210.  
  211.   expr7(valp);
  212.  
  213.   while (*argp != NULL) {
  214.         if (strcmp(*argp, ":") == 0) {
  215.                 ++argp;
  216.                 expr7(&val1);
  217. #ifndef NOCOLON
  218.                 docolon(valp, &val1);
  219. #else
  220.                 valp->nf_valid = 0;
  221.                 valp->strval = NULL;
  222. #endif
  223.         } else
  224.                 break;
  225.   }
  226. }
  227.  
  228. void expr7(valp)
  229. /* [<][>][^][v][top][bottom][index][help] */
  230. struct value *valp;
  231. {
  232.   if (*argp == NULL)
  233.         invalid("missing argument(s)");
  234.   else if (strcmp(*argp, "(") == 0) {
  235.         ++argp;
  236.         expr1(valp);
  237.         if (strcmp(*argp++, ")") != 0) invalid("unbalanced parentheses");
  238.   } else {
  239.         valp->nf_valid = 0;
  240.         valp->strval = *argp++;
  241.   }
  242. }
  243.  
  244. /* Return 1 if the argument is zero (numeric) or null (string */
  245. int nullz(valp)
  246. /* [<][>][^][v][top][bottom][index][help] */
  247. struct value *valp;
  248. {
  249.   if (numvalue(valp)) return(valp->numval == 0);
  250.  
  251.   return(strlen(strvalue(valp)) == 0);
  252. }
  253.  
  254. /* Return 1 if the argument is a valid number, insuring that the nf_valid
  255.  * and numval fields are set properly. Does the string-to-number
  256.  * conversion if nf_valid is false.
  257.  */
  258. int numvalue(valp)
  259. /* [<][>][^][v][top][bottom][index][help] */
  260. struct value *valp;
  261. {
  262.   register char *p;
  263.   int sign = 0, digits = 0;
  264.   unsigned long num = 0;
  265.  
  266.   if (valp->nf_valid) return 1;
  267.  
  268.   if ((p = valp->strval) == NULL) return 0;
  269.  
  270.   if (*p == '-') {
  271.         ++p;
  272.         sign = 1;
  273.   }
  274.   while (isdigit(*p)) {
  275.         num = num * 10 + (*p++ - '0');
  276.         digits = 1;
  277.   }
  278.  
  279.   if (!digits || *p != '\0') return 0;
  280.  
  281.   valp->numval = sign ? -num : num;
  282.   valp->nf_valid = 1;
  283.   return 1;
  284. }
  285.  
  286. /* Return the string value of the given argument. If there is only a
  287.  * numeric value, convert it to a string
  288.  */
  289. char *strvalue(valp)
  290. /* [<][>][^][v][top][bottom][index][help] */
  291. struct value *valp;
  292. {
  293.   char numbuf[30];
  294.   register char *p;
  295.   unsigned long num;
  296.   int sign = 0;
  297.  
  298.   if (!valp->nf_valid) return(valp->strval != NULL) ? valp->strval : "";
  299.  
  300.   p = numbuf + sizeof numbuf;
  301.   *--p = '\0';
  302.  
  303.   if (valp->numval < 0) {
  304.         num = -(valp->numval);
  305.         sign = 1;
  306.   } else
  307.         num = valp->numval;
  308.  
  309.   do {
  310.         *--p = '0' + (num % 10);
  311.         num /= 10;
  312.   } while (num);
  313.  
  314.   if (sign) *--p = '-';
  315.  
  316.   return(valp->strval = strsave(p));
  317. }
  318.  
  319. /* Save the given string in its own allocated memory and return a pointer
  320.  * to that memory.
  321.  */
  322. char *strsave(string)
  323. /* [<][>][^][v][top][bottom][index][help] */
  324. char *string;
  325. {
  326.   char *p;
  327.  
  328.   if ((p = (char *)malloc(strlen(string) + 1)) == NULL) invalid("out of memory");
  329.  
  330.   (void) strcpy(p, string);
  331.  
  332.   return p;
  333. }
  334.  
  335. /* Print error message and exit. */
  336. void invalid(err)
  337. /* [<][>][^][v][top][bottom][index][help] */
  338. char *err;
  339. {
  340.   (void) fputs(progname, stderr);
  341.   (void) fputs(": ", stderr);
  342.   (void) fputs(err, stderr);
  343.   (void) putc('\n', stderr);
  344.   exit(2);
  345. }
  346.  
  347. #ifndef NOCOLON
  348.  
  349. #include <limits.h>
  350.  
  351. #define RMIN            (UCHAR_MAX-8)   /* >= reserved as opcodes */
  352. #define RESC            (UCHAR_MAX-8)   /* for escaping opcodes */
  353. #define RDOT            (UCHAR_MAX-7)   /* match any character */
  354. #define ROPEN           (UCHAR_MAX-6)   /* opening \( */
  355. #define RCLOSE          (UCHAR_MAX-5)   /* closing \) */
  356. #define RSTAR           (UCHAR_MAX-4)   /* Kleene closure */
  357. #define RCLASS          (UCHAR_MAX-3)   /* character class */
  358. #define RBACK           (UCHAR_MAX-2)   /* \digit reference */
  359. #define REND            (UCHAR_MAX-1)   /* end of program */
  360.  
  361. #define RABEGIN         0x01    /* match anchored at BOL (^) */
  362. #define RAEND           0x02    /* match anchored at EOL ($) */
  363. #define RSELECT         0x04    /* \(...\) selection op used */
  364.  
  365. #define PROGLENGTH      1024    /* bytes reserved for r-programs */
  366.  
  367. #define CLASS_BYTES     ((CHAR_MAX - CHAR_MIN + 1 + CHAR_BIT-1) / CHAR_BIT)
  368.  
  369. unsigned char rprogram[PROGLENGTH];     /* regexp program storage */
  370. unsigned int rflags = RABEGIN;  /* regexp program context */
  371.  
  372. char *rbegins[10];              /* pointers to \( beginnings */
  373. char *rends[10];                /* pointers to \) endings */
  374. int rlevel;                     /* \(...\) level */
  375.  
  376. /* Compile the regexp, match it against the string, and return the
  377.  * proper result (a string if \(...\) used, and the match length otherwise.
  378.  */
  379. void docolon(match, pattern)
  380. /* [<][>][^][v][top][bottom][index][help] */
  381. struct value *match, *pattern;
  382. {
  383.   rcomp(strvalue(pattern));
  384.  
  385.   rmatch(strvalue(match));
  386.  
  387.   if (rflags & RSELECT) {
  388.         match->nf_valid = 0;
  389.         if (rends[0] == rbegins[0] || rends[1] == NULL) {
  390.                 match->strval = NULL;
  391.         } else {
  392.                 *(rends[1]) = '\0';     /* semi-nasty */
  393.                 match->strval = rbegins[1];
  394.         }
  395.   } else {
  396.         numresult(match, rends[0] - rbegins[0]);
  397.   }
  398. }
  399.  
  400. /* Compile an ed(1)-syntax regular-expression into the rprogram[] array. */
  401. void rcomp(regexp)
  402. /* [<][>][^][v][top][bottom][index][help] */
  403. register char *regexp;
  404. {
  405.   char c;                       /* current regexp character */
  406.   char first, last;             /* limits of character class */
  407.   unsigned char *starable;      /* last "starable" variable */
  408.   unsigned char *rpc;           /* pointer to next program storage byte */
  409.   int negate;                   /* character class negated */
  410.   int i;                        /* loop counter and such */
  411.   int pstack[9];                /* \(...\) nesting stack */
  412.   int pstackp = 0;              /* stack pointer for nesting stack */
  413.   int pclosed[10];              /* flags indicating \(...\) closed */
  414.  
  415.   rpc = &rprogram[0];
  416.   starable = NULL;
  417.  
  418.   for (i = 1; i < 10; ++i) pclosed[i] = 0;
  419.  
  420.   if (*regexp == '^') {
  421.         rflags |= RABEGIN;      /* not needed, as it turns out */
  422.         ++regexp;
  423.   }
  424.   while ((c = *regexp++)) {
  425.         if ((rpc - rprogram) >= PROGLENGTH - 2 - CLASS_BYTES)
  426.                 invalid("regular expression program too long");
  427.  
  428.         switch (c) {
  429.             case '.':
  430.                 starable = rpc;
  431.                 *rpc++ = RDOT;
  432.                 break;
  433.             case '\\':
  434.                 if (isdigit(*regexp)) {
  435.                         if (!pclosed[*regexp - '0'])
  436.                                 invalid("reference to unclosed/nonexistent \\(...\\) pair");
  437.                         starable = NULL;
  438.                         *rpc++ = RBACK;
  439.                         *rpc++ = *regexp++ - '0';
  440.                 } else if (*regexp == '(') {
  441.                         starable = NULL;
  442.                         ++regexp;
  443.                         rflags |= RSELECT;
  444.                         if ((i = ++rlevel) > 9)
  445.                                 invalid("too many \\(...\\) levels");
  446.                         pstack[pstackp++] = i;
  447.                         *rpc++ = ROPEN;
  448.                         *rpc++ = i;
  449.                         break;
  450.                 } else if (*regexp == ')') {
  451.                         starable = NULL;
  452.                         ++regexp;
  453.                         if (pstackp == 0)
  454.                                 invalid("\\(...\\) pairs don't balance");
  455.                         i = pstack[--pstackp];
  456.                         *rpc++ = RCLOSE;
  457.                         *rpc++ = i;
  458.                         pclosed[i] = 1;
  459.                         break;
  460.                 } else if ((unsigned char) *regexp >= RMIN) {
  461.                         starable = rpc;
  462.                         *rpc++ = RESC;
  463.                         *rpc++ = *regexp++;
  464.                         break;
  465.                 } else {
  466.                         starable = rpc;
  467.                         *rpc++ = *regexp++;
  468.                         break;
  469.                 }
  470.             case '$':
  471.                 if (*regexp == '\0') {
  472.                         rflags |= RAEND;
  473.                         break;
  474.                 } else {
  475.                         starable = rpc;
  476.                         *rpc++ = '$';
  477.                         break;
  478.                 }
  479.             case '*':
  480.                 if (starable == NULL) {
  481.                         starable = rpc;
  482.                         *rpc++ = '*';
  483.                         break;
  484.                 } else {
  485.                         memmove(starable + 1, starable, (size_t)(rpc - starable));
  486.                         *starable = RSTAR;
  487.                         starable = NULL;
  488.                         ++rpc;
  489.                         break;
  490.                 }
  491.             case '[':
  492.                 negate = 0;
  493.                 starable = rpc;
  494.                 *rpc++ = RCLASS;
  495.                 if (*regexp == '^') {
  496.                         ++regexp;
  497.                         negate = 1;
  498.                 }
  499.                 for (i = 0; i < CLASS_BYTES; ++i) rpc[i] = 0;
  500.                 do {
  501.                         first = *regexp++;
  502.                         if (*regexp == '-' && regexp[1] != ']'
  503.                             && regexp[1] > first) {
  504.                                 ++regexp;
  505.                                 last = *regexp++;
  506.                                 for (i = first; i <= last; ++i) {
  507.                                         rpc[(i - CHAR_MIN) / CHAR_BIT] |=
  508.                                                 1 << ((i - CHAR_MIN) % CHAR_BIT);
  509.                                 }
  510.                         } else {
  511.                                 rpc[(first - CHAR_MIN) / CHAR_BIT] |=
  512.                                         1 << ((first - CHAR_MIN) % CHAR_BIT);
  513.                         }
  514.                 } while (*regexp && *regexp != ']');
  515.                 if (*regexp != ']') invalid("unterminated character class");
  516.                 ++regexp;
  517.                 if (negate) for (i = 0; i < CLASS_BYTES; ++i, ++rpc)
  518.                                 *rpc = ~*rpc;
  519.                 else
  520.                         rpc += CLASS_BYTES;
  521.                 break;
  522.             default:
  523.                 if ((unsigned char) c >= RMIN) {
  524.                         starable = rpc;
  525.                         *rpc++ = RESC;
  526.                         *rpc++ = c;
  527.                         break;
  528.                 } else {
  529.                         starable = rpc;
  530.                         *rpc++ = c;
  531.                         break;
  532.                 }
  533.         }
  534.   }
  535.   if (pstackp != 0) invalid("\\(...\\) pairs don't balance");
  536.   *rpc = REND;
  537. }
  538.  
  539. /* It turns out that expr regular expressions have an implicit
  540.  * '^' prepended, and therefore RABEGIN is always on. It seemed
  541.  * a waste to delete the code after discovering this, however.
  542.  */
  543. void rmatch(str)
  544. /* [<][>][^][v][top][bottom][index][help] */
  545. char *str;
  546. {
  547.   char *end;
  548.   unsigned char *rpc;
  549.  
  550.   rends[0] = rbegins[0] = str;
  551.  
  552.   if (rflags & RABEGIN) {
  553.         rpc = &rprogram[0];
  554.         if ((end = rtry(str, &rpc)) != NULL) rends[0] = end;
  555.   } else {
  556.         while (*str) {
  557.                 rpc = &rprogram[0];
  558.                 end = rtry(str, &rpc);
  559.                 if (end != NULL && (end - str) > (rends[0] - rbegins[0])) {
  560.                         rbegins[0] = str;       /* longest match wins */
  561.                         rends[0] = end;
  562.                 }
  563.                 ++str;
  564.         }
  565.   }
  566.  
  567. }
  568.  
  569. /* Try to match str to program from *pcp on */
  570. char *rtry(str, pcp)
  571. /* [<][>][^][v][top][bottom][index][help] */
  572. char *str;
  573. unsigned char **pcp;
  574. {
  575.   char *nstr;
  576.  
  577.   while (*str && **pcp != REND) {
  578.         if ((nstr = tryone(str, pcp)) == NULL) return NULL;
  579.         str = nstr;
  580.   }
  581.  
  582.   while (**pcp == RCLOSE) {
  583.         rends[*(*pcp + 1)] = str;
  584.         *pcp += 2;
  585.   }
  586.  
  587.   if (**pcp != REND) return NULL;
  588.  
  589.   if ((rflags & RAEND) && *str != '\0') return NULL;
  590.  
  591.   return str;
  592. }
  593.  
  594. /* Try to match one regular expression operator */
  595. char *tryone(str, pcp)
  596. /* [<][>][^][v][top][bottom][index][help] */
  597. char *str;
  598. unsigned char **pcp;
  599. {
  600.   char *ret = NULL;
  601.   unsigned char *npc;
  602.   char *p, *q;
  603.  
  604. again:
  605.   switch (**pcp) {
  606.       case RESC:
  607.         if (*str == *(*pcp + 1)) ret = str + 1;
  608.         *pcp += 2;
  609.         break;
  610.       default:
  611.         if (*str == **pcp) ret = str + 1;
  612.         *pcp += 1;
  613.         break;
  614.       case RDOT:
  615.         if (*str != '\0') ret = str + 1;
  616.         *pcp += 1;
  617.         break;
  618.       case RCLASS:
  619.         if (*str != '\0'
  620.             && ((*pcp + 1)[(*str - CHAR_MIN) / CHAR_BIT]
  621.                 & (1 << ((*str - CHAR_MIN) % CHAR_BIT)))) {
  622.                 ret = str + 1;
  623.         }
  624.         *pcp += CLASS_BYTES + 1;
  625.         break;
  626.       case ROPEN:
  627.         rbegins[*(*pcp + 1)] = str;
  628.         *pcp += 2;
  629.         goto again;
  630.       case RCLOSE:
  631.         rends[*(*pcp + 1)] = str;
  632.         *pcp += 2;
  633.         goto again;
  634.       case RBACK:
  635.         p = rbegins[*(*pcp + 1)];
  636.         q = rends[*(*pcp + 1)];
  637.         *pcp += 2;
  638.         while (p < q)
  639.                 if (*p++ != *str++) return NULL;
  640.         ret = str;
  641.         break;
  642.       case RSTAR:
  643.         *pcp += 1;
  644.         p = str;
  645.         while (npc = *pcp, tryone(p, &npc) != NULL) ++p;
  646.         *pcp = npc;
  647.         while (p >= str
  648.                && (npc = *pcp, (ret = rtry(p, &npc)) == NULL))
  649.                 --p;
  650.         *pcp = npc;
  651.         break;
  652.       case REND:        ret = str;
  653. }
  654.  
  655.   return ret;
  656. }
  657.  
  658. #endif                          /* !NOCOLON */
  659. /* [<][>][^][v][top][bottom][index][help] */
  660.